package com.hr.剑指offer.work1;

/**
 * @author 周恒哲
 * @date 2020/06/17
 **/
public class 面试题47_礼物的最大价值 {
    //动态规划
    public int maxValue(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i==0&&j==0){//i==0,j==0
                    continue;
                }
                if (i==0){//i==0,j!=0
                    grid[i][j]+=grid[i][j-1];
                }else if (j==0){//i!=0,j==0
                    grid[i][j]+=grid[i-1][j];
                }else{//i!=0,j!=0
                    grid[i][j]+=Math.max(grid[i][j-1],grid[i-1][j]);
                }
            }
        }
        return grid[m-1][n-1];
    }
}
